/**
*      author: Y_Yao
*      created: 2024-09-16 23:07:21
**/

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 7;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--)
    {
        int n,k,q;
        cin>>n>>k>>q;

        for(int i = 0;i < n;i++)
        {
            cin >> a[i];
            a[i] = a[i] - i - 1;
        }

        vector<int> ret(n+1,0);
        unordered_map<int,int> hash;
        map<int,set<int>> cnt;
        for(int i = 0;i < k;i++)
        {
            int in = a[i];
            if(hash[in]!=0)
                cnt[hash[in]].erase(in);
            hash[in]++;
            cnt[hash[in]].insert(in);
        }

        ret[0] = cnt.rbegin()->first;  
        for(int i = k;i < n;i++)
        {
            int in = a[i];
            if(hash[in]!=0)
                cnt[hash[in]].erase(in);
            hash[in]++;
            cnt[hash[in]].insert(in);

            int out = a[i-k];
            cnt[hash[out]].erase(out);
            hash[out]--;
            if(hash[out]!=0)
                cnt[hash[out]].insert(out);
            if(cnt.rbegin()->second.empty()) cnt.erase(cnt.rbegin()->first);

            ret[i - k + 1] = cnt.rbegin()->first;
        }


        while(q--)
        {
            int l,r;
            cin>>l>>r;
            cout<< k - ret[l - 1]<<endl;
        }
    }
    return 0;
}